package com.mashibing.class04;

/**
 * @Auther: huangxiaode
 * @Date: 2024-01-31 - 01 - 31 - 15:12
 * @Description: com.mashibing.class04
 * @version: 1.0
 */
// 测试链接：https://leetcode.com/problems/reverse-nodes-in-k-group/
public class Code04_ReverseNodesInKGroup {

    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;
    }
    /**
     head : 链表头结点
     k : 链表多少个元素为一组.
     **/
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = head;// 保存链表头
        ListNode end = getKGroupEnd(start, k);	// 从shart开始 数够k个节点之后,返回最后一个节点.
        if (end == null) { // end==null, 当前组没有奏齐.
            return head;
        }
        // 第一组凑齐了！
        head = end;
        reverse(start, end);
        // 执行完reverse函数之后,作为之前的start起始节点变成了尾节点, 上一组的结尾节点
        ListNode lastEnd = start;
        while (lastEnd.next != null) {
            start = lastEnd.next; // 新一组的开头
            end = getKGroupEnd(start, k);// 新一组的结尾.
            if (end == null) {
                return head;
            }
            reverse(start, end);// 链表反转
            lastEnd.next = end; // 上一组的next指针指向此时的end.
            lastEnd = start;	// lastEnd 后移.
        }
        return head;
    }

    // 给定一个开始节点, 你跟我数够k个节点, 把最后一个节点返回.
    // (获取当前组的尾节点)
    public static ListNode getKGroupEnd(ListNode start, int k) {
        while (--k != 0 && start != null) {
            start = start.next;
        }
        return start;
    }
    // 链表反转
    // 给定起始节点和尾节点.
    public static void reverse(ListNode start, ListNode end) {
        end = end.next; // end先来到end的下一个位置.
        ListNode pre = null;	// 记录链表反转之后,当前链表节点的上一个指针.
        ListNode cur = start; // cur来到start位置.
        ListNode next = null; // 记录链表遍历的下移指针
        while (cur != end) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        start.next = end;
    }
}
